#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        vector<int> tmp(nums);
        sort(tmp.begin(), tmp.end(), greater<int>());
        map<int, int> hash;
        for (int i = 0; i < k; i++)
        {
            hash[tmp[i]]++;
        }
        vector<int> res;
        for (auto& e : nums)
        {
            if (hash[e] > 0)
            {
                hash[e]--;
                res.push_back(e);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> idx;
        for (int i = 0; i < n; i++) idx.push_back(i);
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            return nums[a] == nums[b] ? a < b : nums[a] > nums[b];
            });
        vector<bool> vis(n);
        for (int i = 0; i < k; i++) vis[idx[i]] = true;
        vector<int> res;
        for (int i = 0; i < n; i++)
        {
            if (vis[i])
                res.push_back(nums[i]);
        }
        return res;
    }
};